//给定一个单链表 L 的头节点 head ，单链表 L 表示为： 
//
// L0 → L1 → … → Ln-1 → Ln 
//请将其重新排列后变为： 
//
// L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: head = [1,2,3,4]
//输出: [1,4,2,3] 
//
// 示例 2: 
//
// 
//
// 
//输入: head = [1,2,3,4,5]
//输出: [1,5,2,4,3] 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 5 * 104] 
// 1 <= node.val <= 1000 
// 
// Related Topics 栈 递归 链表 双指针 
// 👍 643 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;
public class ReorderList {
    public static void main(String[] args) {
        Solution solution = new ReorderList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        // 找中点
        // 翻转后半段链表
        // 合并
        public void reorderList(ListNode head) {
            ListNode mid = findMid(head);
            ListNode headB = mid.next;
            mid.next=null;
            ListNode newHeadB = reverseList(headB);
            combine(head,newHeadB);
        }
        private ListNode combine(ListNode head, ListNode newHeadB) {
            ListNode hair = new ListNode(-1);
            ListNode hhair = hair;
            while (head!=null && newHeadB!=null){
                hair.next = head;
                head = head.next;
                hair.next.next = newHeadB;
                newHeadB = newHeadB.next;
                hair = hair.next.next;
            }
            if (head==null){
                hair.next = newHeadB;
            }else {
                hair.next = head;
            }
            return hhair.next;
        }
        private ListNode reverseList(ListNode headB) {
            ListNode pre = null;
            ListNode cur = headB;
            while (cur!=null){
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
        public ListNode findMid(ListNode head){
            if (head==null || head.next==null){
                return head;
            }
            ListNode slow = head;
            ListNode fast = head;
            while (fast!=null){
                if (fast.next==null || fast.next.next==null){
                    break;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}